跳到主要内容

丰富的序列

序列的分类​

按元素类型分​

Python 标准库用 C 实现了丰富的序列类型，列举如下。

  • 容器序列 container sequence： 能 存放不同类型 数据的序列

    • list、tuple 和 collections.deque

  • 扁平序列 flat sequence：只能容纳一种类型 的序列

    • str、bytes、bytearray、memoryview 和 array.array

⭐ 容器序列 存放的是所包含对象的引用，而 扁平序列 里在自己的内存空间中直接存储所含内容的值。

image.png|834

换句话说，扁平序列其实是一段连续的内存空间。由此可见扁平序列其实更加紧凑，处理速度更快，但是它里面只能存放原始机器值，例如字节、整数和浮点数。

任何 Python 对象在内存中都有一个包含元数据的标头。最简单的 Python 对象，例如一个 float，内存标头中有一个值字段和两个元数据字段。

  • ob_refcnt：对象的引用计数。
  • ob_type：指向对象类型的指针。
  • ob_fval：一个 C 语言 double 类型值，存放 float 的值。

按可变性分​

序列类型还能按照可变性来分类。

  • 可变序列：list、bytearray、array.array、collections.deque 和 memoryview。
  • 不可变序列 tuple、str 和 bytes。

下图显示了可变序列（MutableSequence）和不可变序列（Sequence）的差异，同时也能看出前者从后者那里继承了一些方法。这个 UML 类图列举了 collections.abc 中的几个类（超类在左边，箭头从子类指向超类，斜体名称代表抽象类和抽象方法）

NeatReader-1658976007715

元组​

除了用作不可变的列表，元组还可以用于没有字段名的记录。鉴于后者常常被忽略，我们先来看看元组作为记录的功用。

元组和记录​

元组最大的特征是其不可变性。不可变性实际上暗含多种含义：

  • 元组记录的值不会改变
  • 元组记录的值的顺序不会改变

第二条相当重要，但是常被忽略。有些时候单纯的数值没有意义，只有结合值与该值在序列中的位置才会有明确的意义（例如经纬度记录，抑或是按照一定顺序采集到的数据）。

拆包让元组可以完美地被当作记录来使用

用作“非具名字段”的记录​

元组拆包 Unpacking​

拆包可以以多种方式进行：

  • 平行赋值：对于一个可迭代对象，使用相同数量的变量接收其中的元素
  • * 运算符拆包：* 可以将一个可迭代对象拆包并作为传入函数的参数
  • * 运算符处理剩余元素：* 除了可以拆包可迭代对象外，还可以用于接收不确定数量的拆包结果
    • 非常神奇的功能，类似于 *args。赋值表达式的左边最多只能由一个 *，并且带有 * 运算符的变量总会自动接受合适数量的拆包结果
* 运算符处理剩余元素
>>> a, b, *rest = range(5)
>>> a, b, rest
(0, 1, [2, 3, 4])

>>> a, b, *rest = range(3)
>>> a, b, rest
(0, 1, [2])

>>> a, b, *rest = range(2)
>>> a, b, rest
(0, 1, [])

>>> a, *body, c, d = range(5)
>>> a, body, c, d
(0, [1, 2], 3, 4)

>>> *head, b, c, d = range(5)
>>> head, b, c, d
([0, 1], 2, 3, 4)

嵌套元组拆包​

接受表达式的元组可以是嵌套式的，例如 (a, b, (c, d))。只要这个接受元组的嵌套结构符合表达式本身的嵌套结构，Python 就可以作出正确的对应。

metro_areas = [
    ('Tokyo','JP'.933,(35.689722,139.691667)),  
    ('Delhi NCR', 'IN', 21.935, (28.613889, 77.208889)),
    ('Mexico City', 'MX', 20.142, (19.433333, -99.133333)),
    ('New York-Newark', 'US', 20.104, (40.808611, -74.020386)),
    ('Sao Paulo', 'BR', 19.649, (-23.547778, -46.635833)),
]

print('{:15} | {:^9} | {:^9}'.format('', 'lat.', 'long.'))
fmt = '{:15} | {:9.4f} | {:9.4f}'
for name, cc, pop, (latitude, longitude) in metro_areas: 
    if longitude <= 0:  
        print(fmt.format(name, latitude, longitude))

用作不可变列表​

把元组当作不可变列表使用时请记住，仅当元组中的所有项也都是不可变对象时，才能保证元组值是固定的。在元组上调用 hash(t) 函数可以快速判断元组的值是否固定。如果 t 包含可变的项，则 hash(t) 抛出 TypeError。

Stack Overflow 网站中有一个问题，题为“Are tuples more efficient than lists in Python?”。Python 核心开发人员 Raymond Hettinger 在回答这个问题时指出了元组在性能上的一些优势，总结如下：

  • Python 编译器求解元组字面量时，经过一次操作即可生成元组常量的字节码。求解列表字面量时，生成的字节码将每个元素当作独立的常量推入数据栈，然后构建列表。
  • 给定一个元组 t，tuple(t) 直接返回 t 的引用，不涉及复制。相比之下，给定一个列表 l，list(l) 创建 l 的副本。
  • tuple 实例长度固定，分配的内存空间正好够用。而 list 实例的内存空间要富余一些，时刻准备追加元素。
  • 对元组中项的引用存储在元组结构体内的一个数组中，而列表把引用数组的指针存储在别处。二者不存储在同一个地方的原因是列表可以变长，一旦超出当前分配的空间，Python 就需要重新分配引用数组来腾出空间，而这会导致 CPU 缓存效率较低。

切片​

✔️ 为什么切片和区间会忽略最后一个元素​

  • 当只有最后一个位置信息时，我们也可以快速看出切片和区间里有几个元素：range(3) 和 my_list[:3] 都返回 3 个元素。
  • 当起止位置信息都可见时，我们可以快速计算出切片和区间的长度，用后一个数减去第一个下标（stop - start）即可。
  • 这样做也让我们可以利用任意一个下标来把序列分割成不重叠的两部分，只要写成 my_list[:x] 和 my_list[x:] 就可以了

这些理由对我不是很有说服力……

具有名称标识的切片操作​

slice(startIndex, endIndex, step=1)

这个用法很实用，主要是能够对切片操作进行单独的定义。方便对不同的序列使用相同的切片操作进行切片。同样的，slice 对象也会忽略最后一个元素

纯文本文件形式的收据以一行字符串的形式被解析
>>> invoice = """
... 0....................................................
... 1909  Pimoroni PiBrella                    $17.50    3    $52.50
... 1489  6mm Tactile Switch x20                $4.95    2     $9.90
... 1510  Panavise Jr. - PV-201                $28.00    1    $28.00
... 1601  PiTFT Mini Kit 320x240               $34.95    1    $34.95
... """

>>> SKU = slice(0, 6)
>>> DESCRIPTION = slice(6, 40)
>>> UNIT_PRICE = slice(40, 52)
>>> QUANTITY = slice(52, 55)
>>> ITEM_TOTAL = slice(55, None)

>>> line_items = invoice.split('\n')[2:]
>>> for item in line_items:
...     print(item[UNIT_PRICE], item[DESCRIPTION])
...
    $17.50   Pimoroni PiBrella
     $4.95   6mm Tactile Switch x20
    $28.00   Panavise Jr. - PV-201
    $34.95   PiTFT Mini Kit 320x240

多维切片和省略​

多维切片在处理实际数据时经常用到，例如处理图像数据或者更高维的数据。Python 内置的序列类型均是一维的，因此内置的序列类型仅支持一维的。

[] 运算符里还可以使用以逗号分开的多个索引或者是切片，外部库 NumPy 里就用到了这个特性，二维的 numpy.ndarray 就可以用 a[i, j] 这种形式来获取，抑或是用 a[m:n, k:l] 的方式来得到二维切片。

要正确处理这种 [] 运算符的话，对象的特殊方法 __getitem__ 和 __setitem__ 需要以元组的形式来接收 a[i, j] 中的索引。也就是说，如果要得到 a[i, j] 的值，Python 会调用 a.__getitem__((i, j))。

总的来说，若想实现多维切片，需要实现 __getitem__ 和 __setitem__ 。前者用于读取数据，后者用于赋值。

省略符号（...）则被用于省略无需额外指定的参数。例如，对于一个四维数组，若仅对第一维和最后一维进行切片，在 Numpy 可以写为：

test_list[i, ..., j]
test_list[i:j, ..., k:z]

这些句法上的特性主要是 为了支持用户自定义类或者扩展，比如 NumPy 就是个例子。

为切片赋值​

若赋值的对象是一个切片，则赋值语句的右侧也必须是一个可迭代对象

但是在 Numpy 等库中，则可以直接用单个数值对切片进行赋值，这一操作主要依赖 Numpy 等库中的 broadcast 机制；基于 broadcast 机制，一些 shape 没有完全对应上的情况在 Numpy 中也可以进行赋值和运算

>>> l = list(range(10))
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> l[2:5] = [20, 30]
>>> l
[0, 1, 20, 30, 5, 6, 7, 8, 9]

>>> del l[5:7]
>>> l
[0, 1, 20, 30, 5, 8, 9]

# 从下标 3 开始，每 2 步长替换一次
>>> l[3::2] = [11, 22] 
>>> l
[0, 1, 20, 11, 5, 22, 9]

>>> l[2:5] = 100  
# 如果赋值的对象是一个切片，那么赋值语句的右侧必须是个可迭代对象。即便只有单独一个值，也要把它转换成可迭代的序列。
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only assign an iterable

>>> l[2:5] = [100]
>>> l
[0, 1, 100, 22, 9]

使用 + 和 * 处理序列​

+ 和 * 始终创建一个新对象，绝不更改操作数。

注意 a * n 这种表达式，如果序列 a 中包含可变项，则结果可能出乎意料。例如，使用 my_list = [[]] * 3 初始化一个嵌套列表，得到的结果是一个列表没错，但是嵌套的 3 个引用指向同一个列表，而你或许并不希望如此。

序列的增量赋值​

+= 背后的特殊方法是 __iadd__ （用于“就地加法”）。但是如果一个类没有实现这个方法的话，Python 会退一步调用 __add__ 。考虑下面这个简单的表达式：

>>> a += b

如果 a 实现了 __iadd__ 方法，就会调用这个方法。同时对可变序列（例如 list、bytearray 和 array.array）来说，a 会就地改动，就像调用了 a.extend(b) 一样。但是如果 a 没有实现 __iadd__ 的话，a += b 这个表达式的效果就变得跟 a = a + b 一样了：首先计算 a + b，得到一个新的对象，然后赋值给 a。也就是说，在这个表达式中，变量名会不会被关联到新的对象，完全取决于这个类型有没有实现 __iadd__ 这个方法。

总体来讲，可变序列一般都实现了 __iadd__ 方法，因此 += 是就地加法。而不可变序列根本就不支持这个操作，对这个方法的实现也就无从谈起。

上面所说的这些关于 += 的概念也适用于 *=，后者相对应的是 __imul__。

接下来有个小例子，展示的是 *= 在可变和不可变序列上的作用：

>>> l = [1, 2, 3]
>>> id(l)
4311953800
>>> l *= 2
>>> l
[1, 2, 3, 1, 2, 3]
>>> id(l)
4311953800 # 可变序列的增量赋值，id 不变

>>> t = (1, 2, 3)
>>> id(t)
4312681568
>>> t *= 2
>>> id(t)
4301348296  # 不可变序列的增量赋值，id 改变

✔ 规律：

  • 可变序列的增量赋值，id 不变
  • 不可变序列的增量赋值，id 改变

对不可变序列进行重复拼接操作的话，效率会很低，因为每次都有一个新对象，而解释器需要把原来对象中的元素先复制到新的对象里，然后再追加新的元素。

str 是一个例外，因为对字符串做 += 实在是太普遍了，所以 CPython 对它做了优化。为 str 初始化内存的时候，程序会为它留出额外的可扩展空间，因此进行增量操作的时候，并不会涉及复制原有字符串到新位置这类操作。

✔ 一个有趣的极限情况​

test_tuple = (1, 2, [3, 4])
test_tuple[2] += [5, 6]

上述操作按理来说应当是直接报错，因为元组中的元素不可赋值。但是实际情况是报错的同时，元组包含的列表被修改了。

对上述代码的字节码进行分析可以发现，顺序执行了下述三个操作

  1. 读取 test_tuple[2] 并将其存入栈顶，记为 TOS
  2. 完成操作 TOS += [5, 6]
  3. 将结果存入原位置：test_tuple[2] = TOS

其中，第二步是对 list 进行的操作，由于 list 是可变序列因此该操作不会报错；第三步是对 tuple 进行的操作，由于 tuple 是不可变序列，当尝试赋值时会抛出错误。但是 tuple 中存放的是 list 的引用，因此此时 tuple 中的 list 实际上已经被修改。

上述结果反映：

  1. 将可变对象放置于不可变对象中是十分危险的操作
  2. 上述操作 不是原子操作，因此发生了上述既完成了操作又抛出了错误的结果。 可以看看这段程序的字节码
>>> dis.dis('s[a] += b')
  1           0 LOAD_NAME                0 (s)
              3 LOAD_NAME                1 (a)
              6 DUP_TOP_TWO
              7 BINARY_SUBSCR                      ❶
              8 LOAD_NAME                2 (b)
             11 INPLACE_ADD                        ❷
             12 ROT_THREE
             13 STORE_SUBSCR                       ❸
             14 LOAD_CONST               0 (None)
             17 RETURN_VALUE
  1. 把 s [a] 的值放在栈顶（TOS）。
  2. 执行 TOS += b。如果 TOS 引用一个可变对象，则操作成功。
  3. 赋值 s [a] = TOS。如果 s 是不可变对象，则操作失败。

list.sort 与内置函数 sorted​

list.sort 方法就地排序列表，即不创建副本。返回值为 None，目的就是提醒我们，它更改了接收者（receiver），没有创建新列表。

这是 Python API 的一个重要约定：就地更改对象的函数或方法应该返回 None，让调用方清楚地知道接收者已被更改，没有创建新对象。

例如，random.shuffle(s) 函数也有类似的行为：就地混洗可变序列 s，返回 None。

与之相反，内置函数 sorted 返回创建的新列表。所以它能接受任何可迭代对象作为参数，包括不可变序列和生成器

有序序列的元素查找以及插入​

bisect 模块提供了对有序序列进行元素查找以及插入的方法。

  • bisect.bisect 可以用于元素插入位置查找：寻找一个位置，使得插入待插入元素后，有序序列仍是有序的。
  • bisect.insort 函数则直接将元素插入有序序列中。

bisect() 和 insort() 均有两种形式，分别被命名为 _right，_left。若遇到相等的元素，_right 会将元素插入到序列中相同值的元素的后面，而 _left 则会插入到前面。

bisect 函数其实是 bisect_right 函数的别名

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect.bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']
import bisect
import random

SIZE=7

random.seed(1729)

my_list = []
for i in range(SIZE):
    new_item = random.randrange(SIZE*2)
    bisect.insort(my_list, new_item)
    print('%2d ->' % new_item, my_list)
10 -> [10]
 0 -> [0, 10]
 6 -> [0, 6, 10]
 8 -> [0, 6, 8, 10]
 7 -> [0, 6, 7, 8, 10]
 2 -> [0, 2, 6, 7, 8, 10]
10 -> [0, 2, 6, 7, 8, 10, 10]

insort 跟 bisect 一样，有 lo 和 hi 两个可选参数用来控制查找的范围。它也有个变体叫 insort_left，这个变体在背后用的是 bisect_left。

*当列表不是首选时​

虽然列表既灵活又简单，但面对各类需求时，我们可能会有更好的选择。

比如，要存放 1000 万个浮点数的话，数组（array.array）的效率要高得多，因为数组在背后存的并不是 float 对象，而是数字的机器翻译，也就是字节表述。这一点就跟 C 语言中的数组一样。

再比如说，如果需要频繁对序列做先进先出的操作，deque（双端队列）的速度应该会更快。

如果在你的代码里，包含操作（比如检查一个元素是否出现在一个集合中）的频率很高，用 set（集合）会更合适。set 专为检查元素是否存在做过优化。

本章余下的内容将讨论很多情况下可以取代列表的可变序列类型

数组​

如果我们需要一个 只包含数字 的列表，那么 array.array 比 list 更高效。

数组支持所有跟可变序列有关的操作，包括 .pop、.insert 和 .extend。另外，数组还提供从文件读取和存入文件的更快的方法，如 .frombytes 和 .tofile。

from array import array  
test_array = array(type, data)
一个浮点型数组的创建、存入文件和从文件读取的过程
>>> from array import array  
>>> from random import random
>>> floats = array('d', (random() for i in range(10**7)))  
>>> floats[-1]  
0.07802343889111107
>>> fp = open('floats.bin', 'wb')
>>> floats.tofile(fp)  
>>> fp.close()
>>> floats2 = array('d')  
>>> fp = open('floats.bin', 'rb')
>>> floats2.fromfile(fp, 10**7)  
>>> fp.close()
>>> floats2[-1]  
0.07802343889111107
>>> floats2 == floats  
True

一个小试验告诉我，用 array.fromfile 从一个二进制文件里读出 1000 万个双精度浮点数只需要 0.1 秒，这比从文本文件里读取的速度要快 60 倍，因为后者会使用内置的 float 方法把每一行文字转换成浮点数。

另外，使用 array.tofile 写入到二进制文件，比以每行一个浮点数的方式把所有数字写入到文本文件要快 7 倍。另外，1000 万个这样的数在二进制文件里只占用 80 000 000 个字节（每个浮点数占用 8 个字节，不需要任何额外空间），如果是文本文件的话，我们需要 181 515 739 个字节。

memoryview 内存视图​

memoryview 是一个内置类，它能让用户 在不复制内容的情况下操作同一个数组的不同切片。

实际上提供了一种在不需要赋值内容的前提下，实现 不同数据结构之间的内存共享。即指定一块区域，能够使用不同的方式去存读数据

例如可以以 list 的形式创建一个序列，然后以 Numpy array 的形式去处理这个序列，而不需要额外再创建一个包含相同内容的新 array。

>>>v = memoryview(bytearray("abcefg", 'utf-8'))
>>> print(v[1])
98
>>> print(v[-1])
103
>>> print(v[1:4])
<memory at 0x10f543a08>
>>> print(v[1:4].tobytes())
b'bce'

双向队列​

利用 .append 和 .pop 方法，我们可以把列表当作栈或者队列来用（比如，把 .append 和 .pop(0) 合起来用，就能模拟栈的“先进先出”的特点）。

但是删除列表的第一个元素（抑或是在第一个元素之前添加一个元素）之类的操作是很耗时的，因为这些操作会牵扯到移动列表里的所有元素。

collections.deque 类（双向队列）是一个线程安全、可以快速从两端添加或者删除元素的数据类型。

而且如果想要有一种数据类型来存放“最近用到的几个元素”，deque 也是一个很好的选择。

这是因为在新建一个双向队列的时候，你可以指定这个队列的大小，如果这个队列满员了，还可以从反向端删除过期的元素，然后在尾端添加新的元素。

from collections import deque

dq = deque(range(10), maxlen=10)
print(dq)
# ------------------ 旋转元素 ------------------0
print("\n将后3个数移动到队列头部:")
dq.rotate(3)
print(dq)
print("\n将前4个数移动到队列尾部:")
dq.rotate(-4)
print(dq)
print("\n从头部添加元素：")
dq.appendleft(-1)
print(dq)
print("\n从尾部添加元素：")
dq.append(-1)
print(dq)
print("\n从尾部逐项添加元素：")
dq.extend([10, 20, 30, 40])
print(dq)
print("\n从头部逐项添加元素：")
dq.extendleft([10, 20, 30, 40])
print(dq)

output

deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)

将后3个数移动到队列头部:
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)

将前4个数移动到队列尾部:
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)

从头部添加元素：
deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)

从尾部添加元素：
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, -1], maxlen=10)

从尾部逐项添加元素：
deque([5, 6, 7, 8, 9, -1, 10, 20, 30, 40], maxlen=10)

从头部逐项添加元素：
deque([40, 30, 20, 10, 5, 6, 7, 8, 9, -1], maxlen=10)

双向队列实现了大部分列表所拥有的方法，也有一些额外的符合自身设计的方法，比如说 popleft 和 rotate。但是为了实现这些方法，双向队列也付出了一些代价，从队列中间删除元素的操作会慢一些，因为它只对在头尾的操作进行了优化。

append 和 popleft 都是原子操作，也就说是 deque 可以在多线程程序中安全地当作先进先出的栈使用，而使用者不需要担心资源锁的问题。

其他​

  • 对 seq[start:stop:step] 进行求值的时候，Python 会调用 seq.__getitem__(slice(start, stop, step))

  • key 参数能让你对一个混有数字字符和数值的列表进行排序。你只需要决定到底是把字符看作数值，还是把数值看作字符：

    >>> l = [28, 14, '28', 5, '9', '1', 0, 6, '23', 19]
    >>> sorted(l, key=int)
    [0, '1', 5, 6, '9', 14, 19, '23', 28, '28']
    >>> sorted(l, key=str)
    [0, '1', 14, 19, '23', 28, '28', 5, 6, '9']